package ljl.alg.wangzheng_camp.round1.slidingwindow;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 题号 438，非常吉利的一个数字
 * 明天再说吧，今天累
 *
 * 看完答案，发觉这个题是在是不应该不会做
 *
 * */
public class _438_find_anagram {
    
    /*
    * 优雅，太优雅了
    * */
    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (p.length() > s.length()) return res;
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < p.length(); i++) {
            sCount[s.charAt(i) - 'a']++;
            pCount[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(sCount, pCount)) res.add(0);
        for (int i = 0, len = s.length() - p.length(); i < len; i++) {
            sCount[s.charAt(i) - 'a']--;
            sCount[s.charAt(i + p.length()) - 'a']++;
            if (Arrays.equals(sCount, pCount)) res.add( i + 1);
        }
        return res;
    }
    /**
     * 操
     * 背错了
     * */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (p.length() > s.length()) return res;
        int[] dic = new int[26];
        for (int i = 0; i < p.length(); i++) {
            dic[p.charAt(i) - 'a']--;
            dic[s.charAt(i) - 'a']++;
        }
        int diff = 0;
        for (int i : dic) {
            if (i != 0) diff++;
        }
        if (diff == 0) res.add(0);
        for (int i = 0, len = s.length() - p.length(); i < len; i++) {
            int left = s.charAt(i) - 'a', right = s.charAt(i + p.length()) - 'a';
            if (dic[right] == -1) diff--;
            else if (dic[right] == 0) diff++;
            dic[right]++;
            
            if (dic[left] == 1) diff--;
            else if (dic[left] == 0) diff++;
            dic[left]--;
            
            if (diff == 0) res.add(i + 1);
        }
        return res;
    }
    
    class answer_not_bad {
        
        public List<Integer> findAnagrams(String s, String p) {
            if (p.length() > s.length())
                return Collections.emptyList();
        
            int[] dict = new int[26];
            for (int i = 0; i < p.length(); i++) {
                dict[s.charAt(i) - 'a']++;
                dict[p.charAt(i) - 'a']--;
            }
        
            List<Integer> res = new ArrayList<>();
        
            int diff = 0;
            for (int j : dict) {
                if (j != 0) diff++;
            }
            if (diff == 0)
                res.add(0);
        
            for (int i = 0; i < s.length() - p.length(); i++) {
                if (dict[s.charAt(i) - 'a'] == 1)
                    diff--;
                else if (dict[s.charAt(i) - 'a'] == 0)
                    diff++;
                dict[s.charAt(i) - 'a']--;
            
                if (dict[s.charAt(i + p.length()) - 'a'] == -1)
                    diff--;
                else if (dict[s.charAt(i + p.length()) - 'a'] == 0)
                    diff++;
                dict[s.charAt(i + p.length()) - 'a']++;
            
                if (diff == 0)
                    res.add(i + 1);
            }
        
            return res;
        }
        
        /*
         * 普通青年的滑动窗口
         * */
        public List<Integer> findAnagrams2(String s, String p) {
            int sLen = s.length(), pLen = p.length();
        
            List<Integer> ans = new ArrayList<>();
            if (sLen < pLen) return ans;
        
            int[] sCount = new int[26];
            int[] pCount = new int[26];
            for (int i = 0; i < pLen; ++i) {
                ++sCount[s.charAt(i) - 'a'];
                ++pCount[p.charAt(i) - 'a'];
            }
        
            if (Arrays.equals(sCount, pCount)) {
                ans.add(0);
            }
        
            for (int i = 0; i < sLen - pLen; ++i) {
                --sCount[s.charAt(i) - 'a'];
                ++sCount[s.charAt(i + pLen) - 'a'];
            
                if (Arrays.equals(sCount, pCount)) {
                    ans.add(i + 1);
                }
            }
        
            return ans;
        }
        
    }
}
